class code5 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b)-> nums1[a[0]]+nums2[a[1]] - (nums1[b[0]]+nums2[b[1]]));
        //num1所有下标入堆，num2所有索引目前都为0
        for(int i=0;i<nums1.length;i++) {
            heap.offer(new int[]{i,0});
        }

        List<List<Integer>> ret = new ArrayList<>();

        //出堆+入num2索引
        while(k--!=0 && !heap.isEmpty()) {
            //最小的出堆
            int[] x = heap.poll();
            //结果+1 
            ret.add(Arrays.asList(nums1[x[0]],nums2[x[1]]));

            //nums2索引+1入堆
            if(++x[1] < nums2.length) {
                heap.offer(x);
            }
        }

        return ret;
    }
}